/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2018年12月26日
*   描    述：
*   Copyright (C) 2018 All rights reserved.
*   
================================================================*/


#include <iostream>
#include <vector>
#include <queue>

using namespace std;

/**
 * Definition for binary tree with next pointer.
  struct TreeLinkNode {
   int val;
   TreeLinkNode *left, *right, *next;
   TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
  };
*/
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if( !root ) 
            return;

        TreeLinkNode *cur = NULL;
        TreeLinkNode *next = NULL;
        int size = 0;
        queue<TreeLinkNode *> st;
        queue<TreeLinkNode *> tmp;
        st.push(root);
        while( !st.empty() ){
            size = st.size();
            while( size ){
                cur = st.front();
                st.pop();
                tmp.push(cur);
                if( cur->left )
                    st.push(cur->left);
                if( cur->right )
                    st.push(cur->right);

                size--;
            }

            cur = tmp.front();
            tmp.pop();
            while( !tmp.empty() ){
                next = tmp.front();
                tmp.pop();
                cur->next = next;
                cur = next;
            }
            cur->next = NULL;
            
        }
    }
};

class Solution {
public:
    void connect(TreeLinkNode *root) {
        if( !root ) 
            return;
        
 	 	TreeLinkNode *cur = root;
        TreeLinkNode *pre = root;
		TreeLinkNode *next = pre->left; 
        while( next ){
            cur = pre;
            while( cur ){
                cur->left-next = cur->right;
                if( cur->right && cur->next )
                    cur->right->next = cur->next->left;
                cur = cur->next;
            }
            
            pre = next;
            next = next->left;
        }
    }
};










